import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LENOVO
 * Date: 2024-08-15
 * Time: 18:58
 */
public class Test {
    //直接选择排序
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[] array,int i,int minIndex) {//传入两下标，互换数组下标值
        int tmp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = tmp;
    }
    //----------------------------------------------------------
    //堆排序   大根堆
    public static void createHeapChild(int[] array,int parent){
        siftDown(array,parent, array.length);
    }
    public static void siftDown(int[] array,int parent,int length){
        int child = 2 * parent + 1;//父节点的子节点
        while(child < length){//一直到最后的子节点为止
            if(child + 1 < length && array[child + 1] > array[child]){//每次当child合法进来时，判断是否有右节点，
                                                                      // 并且使child等于最大子节点的下标
                child += 1;
            }
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent =child;
                child = 2 * parent+ 1;
            }else{
                break;
            }
        }
    }
    public static void createHeap(int[] array){//创建大根堆
        int parent = ((array.length - 1) - 1) / 2;//最后一个父节点
        for (int i = parent; i >= 0; i--) {
            createHeapChild(array,i);//一个一个父节点的创建
        }
    }
    public static void heapSort(int[] array){
        int length = array.length;
        int child = array.length -1;//最后的节点
        while (child > 0){
            swap(array,0,child);//交换堆顶元素到最后的那个子节点，这样最后的节点就是最大的（因为是大根堆）
            length--;
            siftDown(array,0,length);
            child--;
        }
    }
    //----------------------------------------------------
    //快速排序
    public static int split(int[] array,int left,int right){//该方法用于返回基准值，并作一次局部的快速排序
        int leftTemp =left;//记录left位置的值，后面要交换
        int tmp = array[left];//记录left的下标
        while(left < right){//循环直到left == right，即left,right相遇为止
            while(left < right && array[right] >= tmp){//从右侧找起找小于的，只要右侧不小于tmp，就减减,用while找到为止
                right--;
            }
            while(left < right && array[left] <= tmp){//再从左侧开始找大于的
                left++;
            }
            if(left < right){
                swap(array, left, right);
            }
        }
        swap(array,leftTemp,left);
        return left;
    }
    public static void quickSort(int[] array){
        quick(array,0, array.length - 1);
    }
    public static void quick(int[] array,int start,int end){//由于如果我们在quickSort方法里递归，那么我们无法初始化start和end，
                                                            // 所以我们新做一个方法以参数形式接受start和end的初始值即可
        if(start >= end){//当分割到最左边只剩一个的时候，start == end
                         //[1,2]假设这是分割出来的最左边，2是基准值，那么会有quick(0,0) 和quick(2,1),直接返回，说明这排完了
            return;
        }
        int benchmark = split(array,start,end);//找出基准值的下标位置，<进行局部快速排序>
        quick(array, start, benchmark - 1);//基准值左侧，更新了end位置->(对左侧进行快速排序)
        quick(array, benchmark + 1, end);//基准值右侧，更新了start位置

    }
    //----------------------------------------------------
    //插入排序
    //----------------------------------------------------
    //希尔排序
    //----------------------------------------------------
    public static void main(String[] args) {
        int[] arr = new int[]{2,5,6,7,8,9,1,43,0};
        /*selectSort(arr);*/
/*        createHeap(arr);
        heapSort(arr);
        System.out.println(Arrays.toString(arr));*/
        int[] array = {4, 10, 3, 5, 1};
        quickSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}
